package com.leetcode.algorithm.y22.m09.w4;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 2099. 找到和最大的长度为 K 的子序列
 * 
 * https://leetcode.cn/problems/find-subsequence-of-length-k-with-the-largest-sum/
 * 
 * @author jie.deng
 *
 */
class Question2099Solution01 {

	public int[] maxSubsequence(int[] nums, int k) {
		int len = nums.length;
		// 优先队列，元素为二元组(nums[i], i)，排序规则是优先nums[i]逆序相等则按照i升序
		PriorityQueue<int[]> queue = new PriorityQueue<>(k,
				(arr1, arr2) -> arr2[0] == arr1[0] ? arr1[1] - arr2[1] : arr2[0] - arr1[0]);
		for (int i = 0; i < len; i++) {
			queue.offer(new int[] { nums[i], i });
		}

		int[] idxArr = new int[k];
		for (int i = 0; i < k; i++) {
			idxArr[i] = queue.poll()[1];
		}
		Arrays.sort(idxArr);

		int[] result = new int[k];
		for (int i = 0; i < k; i++) {
			result[i] = nums[idxArr[i]];
		}
		return result;
	}

}